package com.yan_jiu_sheng.daily.AC;

import java.util.ArrayList;
import java.util.List;

/**
 * https://leetcode.cn/problems/falling-squares/description/?envType=daily-question&envId=2024-07-28
 * 暴力通过
 * 其他方法：线段树
 *
 * @author yulongtian
 * @create 2024-07-28 10:32
 */
public class Test20240728 {
    public static void main(String[] args) {

    }

    /**
     * 暴力解法
     *
     * @param positions
     * @return
     */
    public List<Integer> fallingSquares(int[][] positions) {
        int n = positions.length;
        List<Integer> res = new ArrayList<Integer>();
        for (int i = 0; i < n; i++) {
            int left1 = positions[i][0];
            int right1 = positions[i][0] + positions[i][1] - 1;
            int height = positions[i][1];
            for (int j = 0; j < i; j++) {
                int left2 = positions[j][0];
                int right2 = positions[j][0] + positions[j][1] - 1;
                if (right1 >= left2 && right2 >= left1) {
                    height = Math.max(height, res.get(j) + positions[i][1]);
                }
            }
            res.add(height);
        }

        for (int i = 1; i < n; i++) {
            res.set(i, Math.max(res.get(i), res.get(i - 1)));
        }

        return res;
    }

}
